package org.example;

import java.util.ArrayList;
import java.util.List;

class MyPs {
    private List<Integer> lst;
    private List<Integer> rs;

    public MyPs (List<Integer> lst, List<Integer> rs) {
        this.lst = lst;
        this.rs = rs;
    }

    public MyPs () {}

    public List<Integer> getLst() {
        return lst;
    }

    public void setLst(List<Integer> lst) {
        this.lst = lst;
    }

    public List<Integer> getRs() {
        return rs;
    }

    public void setRs(List<Integer> rs) {
        this.rs = rs;
    }
}

class MyParams {
    private MyPs left;
    private MyPs mid;
    private MyPs right;

    public MyParams(MyPs left, MyPs mid, MyPs right) {
        this.left = left;
        this.mid = mid;
        this.right = right;
    }

    public MyParams() {}

    public MyPs getLeft() {
        return left;
    }

    public void setLeft(MyPs left) {
        this.left = left;
    }

    public MyPs getMid() {
        return mid;
    }

    public void setMid(MyPs mid) {
        this.mid = mid;
    }

    public MyPs getRight() {
        return right;
    }

    public void setRight(MyPs right) {
        this.right = right;
    }
}

/**
 * 尾递归
 * 模拟递归
 * */
public class MyRecur {
    private List<MyParams> stack = new ArrayList<>();

    public List<MyParams> getStack() {
        return stack;
    }

    public void setStack(List<MyParams> stack) {
        this.stack = stack;
    }

    /**
     * 初始压栈
     * */
    public void Initi(List<Integer> lst) {
        MyStack(lst);
    }

    /**
     * 压栈
     * */
    public void MyStack(List<Integer> lst) {
        if (lst != null && !lst.isEmpty() && lst.size() > 0) {
            if(lst.size() == 1) {
                this.stack.add(new MyParams(new MyPs(lst, null), null, null));
            } else {
                Integer i = lst.get(0);
                List<Integer> mid = new ArrayList<>();
                mid.add(i);
                List<Integer> lst1 = new ArrayList<>();
                List<Integer> lst2 = new ArrayList<>();
                for (int index = 1; index < lst.size(); index++) {
                    if (lst.get(index) < i) {
                        lst1.add(lst.get(index));
                    } else {
                        lst2.add(lst.get(index));
                    }
                }
                this.stack.add(new MyParams(new MyPs(lst1, null), new MyPs(mid, null), new MyPs(lst2, null)));
            }
        }
    }

    /**
     * 连续压栈
     * */
    public void PushStack() {
        if (this.stack.size() > 0) {
            while (true) {
                MyParams last = this.stack.get(this.stack.size() - 1);
                MyPs left = last.getLeft();
                //MyPs mid = last.getMid();
                MyPs right = last.getRight();

                if ((left == null || left.getLst() == null || left.getLst().size() == 0) && (right == null || right.getLst() == null || right.getLst().size() == 0)) {
                    break;
                }

                if (left != null && left.getRs() == null && left.getLst() != null && left.getLst().size() > 0) {
                    this.MyStack(left.getLst());
                }

                if (right != null && right.getRs() == null && right.getLst() != null && right.getLst().size() > 0) {
                    this.MyStack(right.getLst());
                }

            }
        }
    }

}




























